public class code1 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */

    // [1,2,4,7,3,5,6,8] 前序遍历
    // [4,7,2,1,5,3,8,6] 中序遍历
    public TreeNode reConstructBinaryTree (int[] pre, int[] vin) {
        // write code here
        // 先来判断一下两个数组是否为 null 的情况
        if (pre == null || pre.length == 0) {
            return null;
        }
        if (vin == null || vin.length == 0) {
            return null;
        }

        // 可以知道的是，前序遍历的第一个位置就是树的根
        TreeNode root = new TreeNode(pre[0]);

        // 这里在中序遍历中找一下根节点
        int index = FindRoot(pre, vin);

        /**
         * 这里说明一下 copyOfRange 这个方法的作用
         * 这个方法就是将数组进行分割 copyOfRange(T[] original, int from, int to)
         * 比如 [1,2,3,4,5,6,7,8]
         * from = 2, to = 5
         * 最终获取到的值就是 {3,4,5}
         * 可以说这里是 左闭右开 的！！！
         */

        // 这里通过递归的形式来构建树
        // 针对左子树，可以通过 前序遍历的节点的值 将 中序遍历后的数组进行分割，可以细分为左右部分然后实现树的构建操作
        root.left = reConstructBinaryTree(
                Arrays.copyOfRange(pre, 1, index + 1),
                Arrays.copyOfRange(vin, 0, index)
        );
        // 针对右子树，同样的 直接将 前序遍历的右半部分部分的值 和 中序遍历右半部分的值分到一起然后找到树的节点
        root.right = reConstructBinaryTree(
                Arrays.copyOfRange(pre, index + 1, pre.length),
                Arrays.copyOfRange(vin, index + 1, vin.length)
        );


        return root;
    }

    // 这里通过前序遍历的第一个点位在中序遍历的数组中找到 根 节点的位置
    private static int FindRoot(int[] p, int[] v) {
        for (int i = 0; i < v.length; i++) {
            if (p[0] == v[i]) {
                return i;
            }
        }
        return 0;
    }
}
